#ifndef GRAPHEXPLORATION_H
#define GRAPHEXPLORATION_H

#include <vector>
#include "GraphHandler.hpp"

/*
This class allows the user to run a simulated "walk" in a graph.
You feed it a graph in which to walk, and optionally a "partial graph" which has already been explored
It allows you to enumerate all possible next "edit operations" from this partial graph, where an operation is defined as
   * Adding an edge between two existing vertices in the partial graph
   * Adding a vertex which is in the neighborhood of some existing vertex and an edge to that vertex
  */

class GraphExploration
{
public:

    GraphExploration(const GraphHandler::Graph& G);
    GraphExploration(const GraphHandler::Graph& G, const GraphHandler::Graph& gPartial);

    GraphHandler::Graph GetPartialGraph() { return m_PG; }


    class EditOpIterator
    {
    private:
        friend class GraphExploration;
        GraphExploration* m_GE;
        const GraphHandler::Graph* m_G;
        // First component is the vertex of the already existing vertex (in the partial graph), second is
        // that vertex in m_G. For usage if we want to instantiate this particular edit operation.
        pair<GraphHandler::Vertex, GraphHandler::Vertex> m_LastVOp;

        // Which vertices (in the partial graph) that should be connected
        pair<GraphHandler::Vertex, GraphHandler::Vertex> m_LastEOp;

        // First component is if last operation was vertex op, second is edge op
        // false, false means there was no last
        pair<bool, bool> m_LastOp;

        // A vector of vertices from m_pG not yet added to the partial graph
        // also we remove from this each time we step forward with the edit operations
        std::vector<GraphHandler::Vertex> m_kNotAdded;

        // A vector of edges from m_pG not yet added to the partial graph, also we remove from
        // this each time we step forward with the edit operations
        std::vector<GraphHandler::Edge> m_kNotAddedEdges;

        // Internal counter to keep track of how many vertex/edge ops there are left
        int iVOpsLeft;
        int iEOpsLeft;
    public:

        EditOpIterator(void) { m_GE = NULL; iEOpsLeft = -1; iVOpsLeft = -1; m_LastOp = make_pair(false, false); }
        EditOpIterator(const EditOpIterator& i) { iEOpsLeft = -1; iVOpsLeft = -1; m_GE = i.m_GE; m_G = i.m_G; m_kNotAdded = i.m_kNotAdded; m_kNotAddedEdges = i.m_kNotAddedEdges; m_LastOp = make_pair(false, false); }
        EditOpIterator(GraphExploration& GE);

        // Gives the graph with the current edit operation performed
        // The underlying graph is ofcourse the same, however the partial graph is expanded
        GraphExploration& operator*(void); //return (std::vector<int>&) partition->currPart; }

        // Moves to the next possible edit operation
        //EditOpIterator operator++(void);

        pair<GraphHandler::Vertex, GraphHandler::Vertex> NextVertexOp(bool bForceAdd = false);
        pair<unsigned int, unsigned int> NextEdgeOp();
        /*
                    bool operator==(Iterator op2)
                            { if(partition&&op2.partition) {
                                    return (partition->currPart==op2.partition->currPart) ?
                                    true : false; }
                            else {
                                    return (partition==op2.partition) ? true : false; } }
                    bool operator!=(Iterator op2) { return !(*this==op2); }*/


        // Returns the number of vertex operations left
        int VertexOperations();

        // Returns the number of edge operations left
        int EdgeOperations();

        // Returns true if there are no more vertex edit operations, false otherwise
        bool isDoneVertex();

        // Returns true if there are no more edge edit operations, false otherwise
        bool isDoneEdge();
    };
    friend class EditOpIterator;
    friend class AlgorithmStats;

private:
    // The graph which we are exploring
    const GraphHandler::Graph* m_G;

    // The partial graph (what we've seen so far)
    GraphHandler::Graph m_PG;

    // A vector of vertices from m_pG not yet added to the partial graph
    std::vector<GraphHandler::Vertex> m_kNotAdded;

    // A vector of edges from m_pG not yet added to the partial graph
    std::vector<GraphHandler::Edge> m_kNotAddedEdges;

    // Save the correspondence (vertex of m_G) -> (vertex of partial graph m_PG)
    map<GraphHandler::Vertex, GraphHandler::Vertex> m_PGMap;

    // Fills the two vectors m_kNotAdded, m_kNotAddedEdges with all the vertices/edges
    // from m_pG
    void FillNotAdded(const GraphHandler::Graph* pPartial = 0);
};

#endif // GRAPHEXPLORATION_H
